class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left_index = 0
        right_index = len(nums) - 1
        while right_index - left_index >= 2:
            mid_index = (right_index + left_index) // 2
            if nums[mid_index] < nums[mid_index + 1] and nums[mid_index] < nums[mid_index - 1]:
                return nums[mid_index]
            else:
                if nums[mid_index] > nums[left_index] and nums[mid_index] > nums[right_index]:
                    left_index = mid_index + 1
                else:
                    right_index = mid_index - 1
        if right_index == left_index:
            return nums[left_index]
        else:
            return min(nums[left_index], nums[right_index])


data = Solution()
nums = [11,13,15,17]
print(data.findMin(nums))
nums = [4,5,6,7,0,1,2]
print(data.findMin(nums))
nums = [3,4,5,1,2]
print(data.findMin(nums))
nums = [0,1,2]
print(data.findMin(nums))